#include <malloc.h>
#include <stdio.h>

#define MAXVEX 100 // 图中最大顶点个数
#define INF 32767  // 表示∞

typedef char VertexType[10]; // 定义VertexType为字符串类型

typedef struct vertex {
    int adjvex;      // 顶点编号
    VertexType data; // 顶点的信息
} VType;             // 顶点类型

typedef struct graph {
    int n, e;                  // n为实际顶点数,e为实际边数
    VType vexs[MAXVEX];        // 顶点集合
    int edges[MAXVEX][MAXVEX]; // 边的集合
} MatGraph;                    // 图的邻接矩阵类型

// 由邻接矩阵数组A、顶点数n和边数e建立图G的邻接矩阵存储结构
void CreateGraph(MatGraph &g, int A[][MAXVEX], int n, int e) {
    int i, j;
    g.n = n;
    g.e = e;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            g.edges[i][j] = A[i][j];
        }
    }
}

void CreateGraph(MatGraph &g, int n) {
    g.n = n; // 顶点数
    g.e = 0; // 边数
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g.edges[i][j] = INF; // 初始化邻接矩阵为∞
        }
        g.edges[i][i] = 0; // 对角线元素为0
    }
}

void DestroyGraph(MatGraph &g) { // 销毁图
}

// 输出邻接矩阵
void DispMatGraph(const MatGraph &g) {
    int i, j;
    for (i = 0; i < g.n; i++) {
        for (j = 0; j < g.n; j++) {
            if (g.edges[i][j] < INF) {
                printf("%d ", g.edges[i][j]);
            } else {
                printf("%s ", "∞");
            }
        }
        printf("\n");
    }
}

// 输出邻接表
void DispAdjGraph(MatGraph &g) { // 显示图G的结构
    int i, j;
    for (i = 0; i < g.n; i++) {
        printf("%d: ", i); // 输出顶点编号
        for (j = 0; j < g.n; j++) {
            // 如果有边
            if (i != j && g.edges[i][j] < INF) {
                // 输出边的终点编号
                printf("%d[%d]→", j, g.edges[i][j]);
            }
        }
        printf("∧"); 
        printf("\n");
    }
}

int InsertEdge1(MatGraph &g, int u, int v, int w) { // 无向图插入边
    if (u < 0 || u >= g.n || v < 0 || v >= g.n)
        return 0; // 顶点编号错误返回0
    g.edges[u][v] = w;
    g.edges[v][u] = w;
    g.e++;
    return 1;
}

int InsertEdge2(MatGraph &g, int u, int v, int w) { // 有向图插入边
    if (u < 0 || u >= g.n || v < 0 || v >= g.n)
        return 0; // 顶点编号错误返回0
    g.edges[u][v] = w;
    g.e++;
    return 1;
}
